Search results for "Counter machine"

showing 4 items of 4 documents

On a class of languages with holonomic generating functions

2017

We define a class of languages (RCM) obtained by considering Regular languages, linear Constraints on the number of occurrences of symbols and Morphisms. The class RCM presents some interesting closure properties, and contains languages with holonomic generating functions. As a matter of fact, RCM is related to one-way 1-reversal bounded k-counter machines and also to Parikh automata on letters. Indeed, RCM is contained in L-NFCM but not in L-DFCM, and strictly includes L-CPA. We conjecture that L-DFCM subset of RCM

Class (set theory)Holonomic functionsGeneral Computer Science0102 computer and information sciences02 engineering and technologyContext free language01 natural sciencesTheoretical Computer ScienceMorphismRegular language0202 electrical engineering electronic engineering information engineeringParikh vectorMathematicsDiscrete mathematicsk-counter machineHolonomic functionConjecturek-counter machinesSettore INF/01 - InformaticaHolonomicParikh automataComputer Science (all)Context-free languageParikh vectorsAlgebraContext free languagesClosure (mathematics)010201 computation theory & mathematicsBounded function020201 artificial intelligence & image processingHolonomic functions; Parikh vectors; Context free languages; k-counter machines; Parikh automata
researchProduct

One-Counter Verifiers for Decidable Languages

2013

Condon and Lipton (FOCS 1989) showed that the class of languages having a space-bounded interactive proof system (IPS) is a proper subset of decidable languages, where the verifier is a probabilistic Turing machine. In this paper, we show that if we use architecturally restricted verifiers instead of restricting the working memory, i.e. replacing the working tape(s) with a single counter, we can define some IPS’s for each decidable language. Such verifiers are called two-way probabilistic one-counter automata (2pca’s). Then, we show that by adding a fixed-size quantum memory to a 2pca, called a two-way one-counter automaton with quantum and classical states (2qcca), the protocol can be spac…

Counter machineTheoryofComputation_COMPUTATIONBYABSTRACTDEVICESTheoretical computer scienceQuantum registerComputer scienceProbabilistic Turing machineProbabilistic logicInteractive proof systemComputer Science::Computational ComplexityDecidabilityAutomatonsymbols.namesakesymbolsProtocol (object-oriented programming)
researchProduct

Decidability of bisimulation equivalences for parallel timer processes

1993

In this paper an abstract model of parallel timer processes (PTPs), allowing specification of temporal quantitative constraints on the behaviour of real time systems, is introduced. The parallel timer processes are defined in a dense time domain and are able to model both concurrent (with delay intervals overlapping on the time axis) and infinite behaviour. Both the strong and weak (abstracted from internal actions) bisimulation equivalence problems for PTPs are proved decidable. It is proved also that, if one provides the PTP model additionally with memory cells for moving timer value information along the time axis, the bisimulation equivalence (and even the vertex reachability) problems …

Discrete mathematicsCounter machineBisimulationVertex (graph theory)ReachabilityComputer scienceTime domainTimerAlgorithmUndecidable problemDecidability
researchProduct

Unary Languages Recognized by Two-Way One-Counter Automata

2014

A two-way deterministic finite state automaton with one counter (2D1CA) is a fundamental computational model that has been examined in many different aspects since sixties, but we know little about its power in the case of unary languages. Up to our knowledge, the only known unary nonregular languages recognized by 2D1CAs are those formed by strings having exponential length, where the exponents form some trivial unary regular language. In this paper, we present some non-trivial subsets of these languages. By using the input head as a second counter, we present simulations of two-way deterministic finite automata with linearly bounded counters and linear–space Turing machines. We also show …

Discrete mathematicsCounter machineTheoryofComputation_COMPUTATIONBYABSTRACTDEVICESFinite-state machineTheoretical computer scienceUnary operationAbstract family of languagesTheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGESDeterministic finite automatonUnary languageUnary functionComputer Science::Formal Languages and Automata TheoryMathematicsSparse language
researchProduct